package com.demo416_分割等和子集;

import java.util.Arrays;

/**
 * 把一个数组分为和相等的2个子集
 * <p>
 * 这个和把一个数组分成k个相等的子集是一样的做法:
 * <p>
 * 那就是取2个桶, 每个桶的容量 刚好是这个所有元素和的一半.
 * <p>
 * 分别遍历所有的元素, 看看是不是刚好可以放下所有的元素, 如果可以则是true,  否则是false
 * <p>
 * 尝试找一个桶能够刚好装满那么就说明可以这个集合分为两部分
 *
 * 不行, 还是超时了,  使用回溯 超时了
 */
public class Solution_2 {
    public static void main(String[] args) {
        int[] ints = {2, 2, 3, 5};
        boolean b = canPartition(ints);
        System.out.println(b);
    }

    public static boolean canPartition(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 求和
        int sum = Arrays.stream(nums).sum();
        // 求均值
        int average = sum / 2;
        // 特判1
        if (sum % 2 != 0) {
            return false;
        }
        // 特判2
        if (nums[nums.length - 1] > average) {
            return false;
        }
        // 创建2个桶


        // 递归
        boolean result = dfs(nums, average, 0);

        //
        return result;

    }

    private static boolean dfs(int[] nums, int bucket, int startIndex) {
        // 一个桶装满了
        if (bucket == 0) {
            return true;
        }
        // 递归
        for (int i = startIndex; i < nums.length; i++) {
            // 剪枝
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }

            // 桶里还有容量
            if (bucket >= nums[i]) {
                bucket -= nums[i];
                boolean dfs = dfs(nums, bucket, i + 1);
                if (dfs) {
                    return true;
                }
                // 如果走到这里说明上面的这个元素放的有问题,需要取出来
                bucket += nums[i];
            }
        }

        return false;
    }
}
